//
//  main.c
//  C_Study
//
//  Created by rui on 12-8-25.
//  Copyright (c) 2012年 Wang Rui. All rights reserved.
//

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <assert.h>
#include <unistd.h> 

/*
 @要点：链式队列:和静态队列有点不同，第一个（即front）指向的元素的数据是无效，而静态队列是rear指向无效的一个
 */

typedef unsigned int bool;
#define true 1;
#define false 0;

#undef DEBUG
#define DEBUG 1

typedef struct Node{
	int data;
	struct Node *PNext;
}NODE, *PNODE;

typedef struct Queue{
	PNODE front;
	PNODE rear;	
}QUEUE, *PQUEUE;

bool is_empty(PQUEUE pQueue){
	assert(NULL != pQueue);
	return pQueue->front == pQueue->rear;
}

void init(PQUEUE pQueue){
	assert(NULL != pQueue);
	pQueue->front = (PNODE)malloc(sizeof(NODE));
	
	if (NULL == pQueue->front) {
		exit(-1);
	}
	
	pQueue->front->PNext = NULL;
	pQueue->rear = pQueue->front;
}

void in_queue(PQUEUE pQueue,int val){
	assert(NULL != pQueue);

	PNODE pNew = (PNODE)malloc(sizeof(PNODE));
	if (NULL == pNew) {
		exit(-1);
	}
	pNew->PNext = NULL;
	pNew->data = val;
	pQueue->rear->PNext = pNew;
	pQueue->rear = pNew; //此时rear指向队列中最后一个
}


bool out_queue(PQUEUE pQueue,int *popVal){
	assert(NULL != pQueue && NULL != popVal);
	if (is_empty(pQueue)) {
		return false;
	}
	
	PNODE p = pQueue->front;
	*popVal = p->PNext->data;
	pQueue->front = p->PNext;
	free(p);
	
	return true;
}

void travel_queue(PQUEUE pQueue){
	assert(NULL != pQueue);
	printf("Queue:");
	
	PNODE p = pQueue->front;
	while (p != pQueue->rear) {
		printf("%d ",p->PNext->data);
		p = p->PNext;
	}
	
	printf("\n");
}

/**********************************
 *@ main函数
 **********************************/
int main(int argc, const char * argv[])
{
	QUEUE q;
	init(&q);
	int val;
	
	in_queue(&q,5);
	in_queue(&q,4);
	in_queue(&q,3);
	in_queue(&q,2);
	in_queue(&q,1);
	travel_queue(&q);
	
	out_queue(&q,&val);
	printf("%d\n",val);
	
	out_queue(&q,&val);
	printf("%d\n",val);

	travel_queue(&q);
	
	out_queue(&q,&val);
	printf("%d\n",val);
	out_queue(&q,&val);
	printf("%d\n",val);
	out_queue(&q,&val);
	printf("%d\n",val);
	
	travel_queue(&q);
	
	if(out_queue(&q,&val))
	    printf("%d\n",val);
	
	return 0;
}

